package com.cwj.lab1;

import java.util.LinkedList;


/**
 * 循环数组实现的队列；
 * 其实现判断
 * */

public class QueueCy<T> {
    //队列元素数目
    int len;
    //头指针和尾指针
    int frt,back;
    //存放队列的数组
    Object[]nums;
    //构造器
    public QueueCy(int size) {
        this.len = 0;
        frt=back=-1;
        nums=new Object[size];
    }
    public QueueCy() {
        this(14);
    }
    //更新队列的内容
    //扩容
    private void reSize(int size){
        if(size<len){
            throw new RuntimeException("扩容后的长度必须比原来队列元素大，否则后有数据损失");
        }
        Object[]Nums=new Object[size];
        int top=-1,ed=-1;
        int i=0;
        for(i=this.frt;i!=back;i=(i+1)%nums.length){
            Nums[++ed]=this.nums[i];
        }
        if(i==back&&back!=-1){
            Nums[++ed]=this.nums[back];
        }
        if(ed>-1){
            top=0;
        }
        this.frt=top;
        this.back=ed;
        nums=Nums;
    }
/**
 * @param one 将one加入队列
 *            其判断队列是否已满的条件为尾指针+1是否等于头指针
 * */
    public void push(T one){
        int Len=nums.length;
        //判断队列是否已满
        if((back+1)%Len==frt){
            reSize(Len*=2);
            push(one);
            return;
        }
        back=(back+1)%Len;
        nums[back]=one;
        if(frt==-1){
            frt=0;
        }
        len+=1;
    }
    /**
     * 将首元素出队
     * @return 出队的元素
     * */
    @SuppressWarnings("unchecked")
    public T pop(){
        if(frt==-1&&back==-1){
            throw new RuntimeException("队列为空不可删除");
        }
        Object temp=nums[frt];
        if(frt==back){
            frt=back=-1;
        }else{
            frt=(frt+1)%nums.length;
        }
        this.len-=1;
        if(len<nums.length/2){
            reSize(nums.length/2);
        }
        return (T)temp;
    }
    /**
     * 返回队首元素
     * */
    @SuppressWarnings("unchecked")
    public T front(){
        if(this.len<1||frt==-1){
            throw new RuntimeException("队列为空");
        }
        return (T)nums[this.frt];
    }
    /**
     * 返回队尾元素
     * */
    @SuppressWarnings("unchecked")
    public T back(){
        if(this.len<1||back==-1){
            throw new RuntimeException("队列为空");
        }
        return (T)nums[this.back];
    }
    public int size(){
        return this.len;
    }
    public boolean isEmpty(){
        return this.len<=0;
    }

    public void show(){
        System.out.print("{");
        for (int i = 0; i < this.len; i++) {
            System.out.print(this.nums[i]+" ");
        }
        System.out.print("}");
    }

    public static void main(String[] args) {
        QueueCy<Integer> que=new QueueCy<>();
        LinkQueue<Integer> Lque=new LinkQueue<>();
        LinkedList<Integer> testQue=new LinkedList<>();
        for(int i=0;i<30;i+=1){
            int temp=(int)(Math.random()*10);
            System.out.print(i+"次添加："+temp+"\t");
            if((i+1)%5==0){
                System.out.println();
            }
            que.push(temp);
            Lque.push(temp);
            testQue.add(temp);
        }
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`");
        for (int i = 0; i < 30; i++) {
            System.out.println(i+"次删除：QueueCy.pop="+que.pop()+"\tjava标志集合库的，pop="+testQue.poll()+"\tLinkQueue="+Lque.pop());
            System.out.println();
        }
    }
}
